package hash;

public class HashTable {
    // 节点类
    static class Entry {
        int hash; // 哈希码
        Object key; // 键
        Object value; // 值
        Entry next;

        public Entry(int hash, Object key, Object value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }
    Entry[] table = new Entry[16];//给定的数组长度，这里一定要为2的n次方，与下面计算索引位置有关
    int size = 0; // 元素个数
    float loadFactor = 0.75f; // 12 阈值，也就是加载因子
    int threshold = (int) (loadFactor * table.length);//要扩容的长度

    /*根据hash获取value*/
    Object get(int hash, Object key) {
        int idx = hash & (table.length - 1);//计算数据的存储位置
        if (table[idx] == null) {//当该处数据为空时
            return null;
        }
        //下面是找到数据不为空，并且找到该处链表时的查找
        Entry p = table[idx];
        while (p != null) {
            if (p.key.equals(key)) {//注意p的类型，这里一定要使用equals方法来进行比较，
                // 可以避免很多问题，例如给定的key为null或者给定的对象为null(当然这里不会为null，我们已经做了相关的判断).
                return p.value;
            }
            p = p.next;
        }
        return null;//在该处的链表也找不到，那么就没有该值了
    }

    void put(int hash, Object key, Object value) {
        //首先我们要判断是否有该数据
        int idx = hash & (table.length - 1);//计算数据的存储位置
        //1.当该处数据为空时
        if (table[idx] == null) {
            //创建一个新的
            table[idx] = new Entry(hash, key, value);
            size++;
        }else {
            //2.当该处数据不为空时，沿着链表进行查找，接下来的是对该处链表上的操作
            Entry p = table[idx];
            while (true) {
                //向下找
                //2.1若是找到了，则进行该处的值的更新
                //由于没有进行值的添加，所以size不变
                if (p.key.equals(key)) {
                    p.value = value;
                    return;
                }
                //2.2若是到最后还是没有找到
                if (p.next == null) {
                    break;
                }
                p = p.next;//注意这个代码的位置
            }
            //2.3该处的链表也没有该节点，那么就创建一个新的节点，将其加入到该链表处
            p.next = new Entry(hash, key, value);
            size++;
            //看容量实现扩容
            if (size > threshold) {
                resize();
            }
        }
        //可以将上面的两个size都放在这里，减少代码
        //size++;
    }

    public Object remove(int hash, Object key) {
        //首先我们要看是否有该数据
        int idx = hash & (table.length - 1);//计算数据的存储位置
        //若是空，代表不存在，直接返回即可
        if (table[idx] == null) {
            return null;
        }
        //下面是不为空的情况，在链表处查找该key对应的值
        Entry p = table[idx];
        Entry temp=null;
        while (p != null) {
            if (p.key.equals(key)) {
                //找到了。进行删除操作
                //这里是单链表，删除需要知道上一个节点，于是我们找一个临时节点来记录
                //这里有一个特殊情况，当删除的链表切好为第一个节点时，即是头节点
                if (temp == null) {
                    table[idx] = p.next;
                }else {
                    temp.next = p.next;
                }
                size--;//减小数组记录的数量数量
                return p.value;
            }
            temp=p;//记录上一个节点
            p = p.next;
        }
        return null;
    }

    //在达到阈值时进行扩容操作

    void resize() {
        //创建出来一个新容量的新数组
        Entry[] newTable = new Entry[table.length << 1];
       //我们需要对在原数组下的链表进行拆分操作
        for (int i=0;i<table.length;i++){//处理原数组下的每一个链表
            //获取对应数组下的链表的表头
            Entry p = table[i];
            //接下来时对该数组进行一些差分的操作
            /*拆分规律
            * 1.一个原来的链表最多会被拆分为两个，这里可以理解为数组的扩容是按2倍设计影响的
            * 2.hash&table.length==0为一组
            *   hash&table.length!=0为一组*/
            if (p != null) {
                //若是下面有链表，则进行拆分
                Entry a = null;
                Entry b = null;/*链表最多为两个，这里我就定义两个链表，为什么它是null
                 而不是想哨兵节点那样的呢，是因为它可能为null，这样子更加的方便(当然另一种也行)*/
                Entry aHead = null;
                Entry bHead = null;//用于记录其头节点
                //知道对链表遍历完后才结束
                while (p != null) {
                    //对每个节点进行处理，然后拿到需要的两个链表的头节点
                    if ((p.hash&table.length)==0) {
                        //要分为为空和不为空
                        if (a != null) {
                            a.next = p;
                            a = a.next;//向下走
                        }else {
                            aHead = p;
                            a=p;
                        }
                    }else {
                        if (b != null) {
                            b.next = p;
                            b = b.next;
                        }else {
                            bHead = p;
                            b = p;
                        }
                    }
                    p = p.next;
                }
                //在这里进行链表结构的完善(主要是为其在最后添加null)，并且进行链表所在地方的索引的修改
                //为什么是判断a(b)!=null，而不是a(b).next!=null,是为了避免b为空，出现空指针异常的报错，a在这里不为空
                if (a != null) {
                    a.next = null;
                    newTable[i] = aHead;
                }
                // a 链表保持索引位置不变，b 链表索引位置+table.length
                if (b != null) {
                    b.next = null;
                    newTable[i + table.length] = bHead;
                }
            }

        }
        table = newTable;//将修改后的数组赋回去
        threshold = (int) (loadFactor * table.length);//更新阈值
    }


}
